﻿using System;
using System.Collections.Generic;
using System.Globalization;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading.Tasks;

namespace Algorithm.Easy_67_AddBinary
{

    //两个解决思路  
    //1：先转换到BigInteger十进制  加完之后 在转回 二进制
    //2：以字符串位基础，不进行进制转换

    class MainProject
    {
    
        // 暂时未搞定
        static void Main(string[] args)
        {
            Console.WriteLine();
            //string a = "10100000100100110110010000010101111011011001101110111111111101000000101111001110001111100001101";
            //string b = "110101001011101110001111100110001010100001101011101010000011011011001011101111001100000011011110011";
            //string a = "11";
            //string b = "11010010";
            //"1110001"
            string a = "1110001";
            string b = "0011101";
            //string b = "1";
            Console.WriteLine(AddBinary(a, b));
            Console.WriteLine();
            Console.ReadKey();
        }

        //string[i]是只读对象，不可以赋值
        public static string AddBinary(string a, string b)
        {
            //好方法
            if (string.IsNullOrEmpty(a) || string.IsNullOrEmpty(b)) return string.Empty;
            var result = new Stack<char>();
            int sum = 0;
            int i = a.Length - 1;
            int j = b.Length - 1;

            while (i >= 0 || j >= 0)
            {
                sum += i >= 0 ? a[i--] - '0' : 0;
                sum += j >= 0 ? b[j--] - '0' : 0;
                result.Push((sum % 2 == 0) ? '0' : '1');
                //右移一位，留下进位位。
                sum >>= 1;
            }
            if (sum == 1) result.Push('1');
            //倒序输出 栈后进先出
            return new string(result.ToArray());


            #region 进制转换
            //BigInteger aTen = BinaryStringToBigInteger(a);
            //BigInteger bTen = BinaryStringToBigInteger(b);
            //BigInteger sum = aTen + bTen;
            //return ToBinaryString(sum);
            #endregion
        }











        private static BigInteger BinaryStringToBigInteger(string b)
        {
            BigInteger Decimalvalue = 0;
            foreach (char c in b)
            {
                Decimalvalue <<= 1;
                Decimalvalue += c == '1' ? 1 : 0;
            }
            return Decimalvalue;
        }


        public static string ToBinaryString(BigInteger bigint)
        {
            if (bigint == 0)
            {
                return "0";
            }
            var bytes = bigint.ToByteArray();
            var idx = bytes.Length - 1;

            // Create a StringBuilder having appropriate capacity.
            var base2 = new StringBuilder(bytes.Length * 8);

            // Convert first byte to binary.
            var binary = Convert.ToString(bytes[idx], 2);

            // Ensure leading zero exists if value is positive.
            if (binary[0] != '0' && bigint.Sign == 1)
            {
                base2.Append('0');
            }
            base2.Append(binary);
            for (idx--; idx >= 0; idx--)
            {
                base2.Append(Convert.ToString(bytes[idx], 2).PadLeft(8, '0'));
            }
            return base2.ToString().TrimStart('0');
        }
    }
}
